|
Academic Open Internet Journal |
Volume 13, 2004 |
A Novel
Image Compression Algorithm using Ridgelet Transformation with Modified SPIHT
N. Malmurugan
Assistant Professor
Department of Electronics and Communication Engineering
n_malan@mail.com
A. Shanmugam
The Principal
Bannariamman
Institute of Technology, Sathyamanagalam – 638 401,
S. Jayaraman
Professor
A.R. Abdul Rajak
Assistant Professor
Department of Electronics and Communication Engineering
Abstract--An effective image coding technique
which involves transforming the image into another domain with Ridgelet
function and then quantizing the coefficients with modified SPIHT has been
presented in this paper. Ridge functions are effective in representing
functions that have discontinuities along straight lines. Normal Wavelet
transforms fail to represent such functions effectively. SPIHT has been defined
for normal wavelet decomposed images as an embedded quantization process. If
the coefficients obtained from Ridgelet transform of the image with more
discontinuities along straight lines have to subject to quantization process
with SPIHT, the existing structure of the SPIHT should be modified to suit with
the output of the Finite Ridgelet Transform (FRIT) . In this paper, a modified
SPIHT algorithm for FRIT coefficients has been proposed. The results obtained
from the combination of FRIT with modified SPIHT found much better than that
obtained from the combination of Wavelet Transform with SPIHT
Key words-- Ridgelets, Wavelets, Ridge function, Image coding,
Modified SPIHT, Partitioning, and Radon Transform.
A
Novel Image Compression Algorithm using Ridgelet Transformation with Modified
SPIHT
N. Malmurugan , A. Shanmugam, S. Jayaraman , A.R.
Abdul Rajak
Abstract--An effective image coding technique which involves
transforming the image into another domain with Ridgelet function and then
quantizing the coefficients with modified SPIHT has been presented in this
paper. Ridge functions are effective in representing functions that have
discontinuities along straight lines. Normal Wavelet transforms fail to
represent such functions effectively. SPIHT has been defined for normal wavelet
decomposed images as an embedded quantization process. If the coefficients
obtained from Ridgelet transform of the image with more discontinuities along
straight lines have to subject to quantization process with SPIHT, the existing
structure of the SPIHT should be modified to suit with the output of the Finite
Ridgelet Transform (FRIT) . In this paper, a modified SPIHT algorithm for FRIT
coefficients has been proposed. The results obtained from the combination of
FRIT with modified SPIHT found much better than that obtained from the
combination of Wavelet Transform with SPIHT
Index Terms-- Ridgelets, Wavelets, Ridge
function, Image coding, Modified SPIHT, Partitioning, and Radon Transform.
I.
INTRODUCTION
Candes[1],
in 1998 developed a new set of ideas, ridgelet
analysis, for solving important problems such as constructing neural
networks or approximating and estimating multivariate functions by linear
combinations of ridge functions. Candes and Donoho [2], in 1999 introduced the ridgelet transform as a
new multiscale representation for functions on
continuous spaces that are smooth away from discontinuities along lines. Then
Minh N.Do and Martin Vetterli [5] proposed an
Orthonormal version of the ridgelet transform for discrete and finite-size
images. It uses the finite Radon transform proposed by Bolker
[6] (1987) and Matus and Flusser
[7] (1993) as a basic building block. The transform is invertible,
non-redundant and computed via fast algorithms. Furthermore, this construction
leads to a large family of directional and Orthonormal bases for images.
Many
image processing tasks take advantage of sparse representations of image data
where most information is packed into a small number of samples. Typically,
these representations are achieved via invertible and non-redundant transforms.
Currently, the most popular choices for this purpose are the wavelet transform
and the discrete cosine transform.
The success of wavelets is mainly due to the good
performance for piecewise smooth functions in one dimension. Unfortunately,
such is not the case in two dimensions. In essence, wavelets are good at
catching zero-dimensional or point singularities, but two-dimensional piecewise
smooth signals resembling images have one-dimensional singularities.
Intuitively, wavelets in two dimensions are obtained by a tensor-product of one
dimensional (1-D) wavelets and they are thus good at isolating the
discontinuity across an edge, but will not see the smoothness along the edge.
This fact has a direct impact on the performance of wavelets in many applications
[5]. While simple, these methods work very effectively, mainly due to the
property of the wavelet transform that most image information is contained in a
small number of significant coefficients around the locations of singularities
or image edges. However, since wavelets fail to represent efficiently
singularities along lines or curves, wavelet-based techniques fail to explore
the geometrical structure that is typical in smooth edges of images. Therefore,
new image processing schemes which are based on true two-dimensional (2-D)
transforms are expected to improve the performance over the current
wavelet-based methods.
To overcome the weakness of wavelets in higher
dimensions, Candes and Donoho
[2] recently pioneered a new system of representations named ridgelet which
deal effectively with line singularities in 2-D. The idea is to map a line
singularity into a point singularity using the Radon transform. Then, the
wavelet transform can be used to effectively handle the point singularity in
the Radon domain. Their initial proposal was intended for functions defined in
the continuous R2 space.
II.
CONTINOUS & DISCRETE RIDGELET TRANSFORM
CONTINOUS RIDGELET TRANSFORM:
The continuous ridgelet transform of an integrable bivariate function
f(x) is given by
…………………………… (1)
where ridgelets 
in 2-D are defined
from a wavelet type function in 1-D 
as
………………….………. (2)
Wavelets: 
point-position
Ridgelets: 
line-position
The Fig 1 shows the Ridgelet function oriented at an
angle 
and constant along the
lines 
.
Fig 1 Ridgelet Function
In 2-D, points and lines are related through the
Radon transform, thus the wavelet and ridgelet transforms are linked through
the Radon transform. More precisely, denote the Radon transform as
................. (3)
Then the ridgelet transform is the application of a
1-D wavelet transform to the slices (also referred to as projections) of the
Radon transform, and is denoted as
…..………….…..….. (4)
Instead of taking a 1-D wavelet transform on the
radon transform, the application of a 1-D Fourier transform would result in the
2-D Fourier transform. Let 
be the 2-D Fourier
transform of
, and then we have
................................. (5)
This is the famous projection-slice theorem and is commonly used in image
reconstruction from projection methods. In short, the ridgelet transform is the
application of 1-D wavelet transform to the slices of the radon transform,
while the 2-D Fourier transform is the application of 1-D Fourier transform to
those radon slices.
DISCRETE RIDGELET TRANSFORM:
For practical applications, the development of
discrete versions of the ridgelet transform that lead to algorithmic
implementations is a challenging problem. Due to the radial nature of
ridgelets, straightforward implementations based on discretization
of continuous formulae would require interpolation in polar coordinates, and
thus result in transforms that would be either redundant or can not be
perfectly reconstructed. We take up a discrete ridgelet transform proposed by
Minh N. Do and Martin Vetterli [5] that achieves both invertibility
and non-redundancy and its construction leads to a large family of orthonormal
and directional bases for digital images, including adaptive schemes. The
inverse transform is numerically stable and uses the same algorithm as the
forward transform. This discrete version of the Ridgelet Transform uses the
discrete Radon transform discussed earlier to obtain Radon Projections of the
digital image. Then the conventional 1-D Discrete Wavelet Transform is applied
individually on the projections and arranged in a matrix form to result in the
FRIT we are looking for.
III.
ORTHONORMAL FINITE RIDGELET TRANSFORMS
An invertible discrete ridgelet transform can be
obtained by taking the discrete wavelet transform (DWT) on each FRAT projection
sequence 
where the direction 
is fixed. The overall
result is called Finite Ridgelet
Transform as shown in Fig 2. Typically 
is not dyadic,
therefore a special border handling is required. Due to the periodicity
property of the FRAT coefficients for each direction, periodic wavelet
transforms are chosen for
Fig 2 Finite Ridgelet Transform
processing. Since FRAT is redundant and not orthogonal, this
redundancy can be removed by applying 1-D DWT on the projections of the FRAT,
and by this we can obtain an orthonormal transform. For a more general setting,
let us assume that we have a collection of 
1-D orthonormal
transforms on 
(which can be the
same), one for each projection 
of FRAT, that have
bases as
By definition, the FRIT can be written as
…………….….(6)
By applying DWT decomposition applied on the FRAT
projections, all of the non-orthogonality and redundancy
of the FRAT is pushed into the scaling coefficients. When the DWTs are
taken to the maximum number of levels then all of the remaining scaling
coefficients at different projections are the same, hence we can drop all but
one of them. The result is an Orthonormal FRIT.
We prove the above result for the general setting
where different transforms can be applied on different FRAT projections. The
choice of transforms can be either adaptive, depending on the image, or
pre-defined. The orthogonality holds as long as the
all lowpass branch of the general tree-structured
filter bank is decomposed to a single coefficient. All other branches would
contain at least one highpass filter thus leading to
zero-mean basis functions. Due to the wrap around effect of the FRAT, some of
its projections could contain strong periodic components so that a Fourier-type
transform like the DCT might be more efficient.
IV.
PROPOSED IMAGE CODING
TECHNIQUE AND ALGORITHMS USED
In this paper we propose the following coding technique
for images with straight singularities. The proposed model shown in Fig 3 is
very effective in overcoming the shortcomings of the wavelet transform based
coding methods when applied to images with linear edges. The technique is as
follows:
1. Represent the image data as intensity values
of pixels in the spatial co-ordinates.
2. Apply Ridgelet Transform (Orthonormal Ridgelet
Transform, to be specific) on the image matrix and get the Ridgelet coefficients of
the image.
3. Quantize the available coefficients using the SPIHT Algorithm, specially modified for the Orthonormal Ridgelet Transform.
4. Use any
form of entropy coding on the bit stream available from the SPIHT encoder.
MODIFIED SPIHT:
The SPIHT Algorithm as given in the literature is a very
useful tool for uniformly quantizing the coefficients obtained from the wavelet
sub band decomposition of images [8], [9],[10]. It forms
Fig 3 Proposed Image Compression Techniques
Lists using the approximation and Nth level
decomposition detail coefficients and then checks them for significance against
a threshold. Offspring are established using quad tree spatial orientation
structures and then each significant coefficient is bit plane coded in the
order of descending entropy. Roots are coded prior to the offspring.
The problem in applying such an algorithm to the
Ridgelet decomposed image is that the form in which ridgelet decomposes the
image is different from that of wavelets.
1. Also the
wavelet decomposition of Radon Projections in the Ridgelet analysis is not
necessarily dyadic.
2. The
approximation and nth level detail coefficients are arranged in the
transform matrix in a different order. So LIST formation should be changed.
3. Moreover
the offsprings are established in a different format.
So modifications must be made in the normal SPIHT
Algorithm to make it comply with the Ridgelet Transform. The following are the
solutions proposed to address these problems in applying SPIHT to Ridgelet
Transformed image:
1. The
Orthonormal Ridgelet Transform which uses dyadic Decomposition of Radon
Projections to the maximum number of levels is chosen for the coding technique.
2. In
Orthonormal RT we find that each column (Wavelet transformed Radon Projection)
has one Approximation coefficient, one nth level detail coefficient,
two (n-1)th level coefficients, four (n-2)th level coefficients and so on. Hence it can be
seen that all approximation coefficients fall in the 1st row of the
RT image and all nth level detail coefficients fall in the 2nd
row.
Fig 4 List Formation in Modified SPIHT Algorithm
So it is very clear that from Fig 5 that the Modified
SPIHT has different type of list contents against Normal SPIHT as described
below:
In
In Modified SPIHT – LIP contains 1st
and 2nd row which is again approximation coefficients with nth
level detail coefficients. But, LIS will have 2nd row which is nth
level detail coefficients.
3. Every root has its offspring in the same
column, which means that the spatial orientation trees are mapped considering
each column as a 1-D vector individually. Every nth detail
coefficients has two offspring in (n-1)th
detail coefficients set lying in the corresponding position from the top, as
its root is in the nth level detail coefficients set.
Hence as a
generalization offspring can be mapped by the following formula:
O(i,j) = { (2i,j),(2i+1,j) }
Fig 5 Image Decomposition and Offspring dependencies
using Ridgelet Transform
As a result each parent has two offspring in contrast
to the four offspring for each parent in the normal SPIHT encoding. These are
the important changes made in the SPIHT procedure to be used for Ridgelets
(Orthonormal, to be specific).Rest of the procedure is identical to the one
applied to wavelets including thresholding, refinement and decoding. The
changes made in the encoding process must be considered in the decoding process
and appropriately reflected in the inverse way for faithful reconstruction.
V.
RESULTS AND
COMPARISONS
For testing the performance
of the proposed image coding system, the following test images were taken up:
(a) Object (b) Saturn (c)
Truncated
Gaussian
Fig 6 Test Images
These images in Fig 7 were subjected to orthonormal
Ridgelet transform which uses 1-D dyadic wavelet decomposition. Hence it
provided means for SPIHT encoding. The standard parameters like MSE, PSNR and
CR were calculated for various numbers of planes excluded during the SPIHT
encoding. The results obtained are compared with the SPIHT encoded images after
normal 2-D wavelet decomposition up to the equal number of levels. The wavelet
named ‘db1’ was used in both cases.
In the following sections we use the terms “proposed
technique” for Orthonormal FRIT (OFRIT) followed by Modified SPIHT and
“existing technique” for 2-D Wavelet Transform followed by Conventional SPIHT. The subject quality of the Reconstructed
Images from Proposed technique is much better than that from the existing
technique which is much evident from the Fig 10.
The
results given in Table I clearly show the superiority of Ridgelet Transforms
over wavelet transforms with straight edges. Moreover the smooth distribution
of the intensity levels
contributes
to the compaction of most part of the image energy in the low frequency range,
so that the compression becomes much easier and effective. Ridgelets outdo the
wavelets in all parameters taken for comparison for the given object image.
Since the edges are captured in a
TABLE I
Comparison results of OBJECT image
|
No. of bit planes excluded |
CR |
RMSE |
PSNR |
|||
|
Proposed scheme |
Existing scheme |
Proposed scheme |
Existing scheme |
Proposed scheme |
Existing scheme |
|
|
6 |
52.0891 |
67.1132 |
19.8702 |
30.7691 |
24.1152 |
20.2246 |
|
5 |
26.0074 |
31.2467 |
18.9722 |
30.2331 |
24.5735 |
20.5078 |
|
4 |
8.4370 |
16.2444 |
18.6265 |
29.9898 |
25.1293 |
21.0340 |
|
3 |
3.6959 |
9.5448 |
17.3571 |
29.9418 |
25.3914 |
21.0664 |
TABLE II
Comparison results of SATURN image
|
No. of bit planes excluded |
CR |
RMSE |
PSNR |
|||
|
Proposed scheme |
Existing scheme |
Proposed scheme |
Existing scheme |
Proposed scheme |
Existing scheme |
|
|
6 |
63.6080 |
57.9196 |
14.6810 |
19.8392 |
29.0424 |
22.3071 |
|
5 |
43.8937 |
31.5551 |
14.3753 |
19.5026 |
29.4098 |
22.4515 |
|
4 |
20.8719 |
19.1304 |
13.9449 |
19.4416 |
29.1155 |
22.4620 |
|
3 |
7.5464 |
12.3840 |
13.6012 |
19.3265 |
26.6214 |
22.6305 |
very small number of ridgelet coefficients,
the performance is very good even when most of the coefficients are dropped. In
the case of wavelets it is not the same. They fail in capturing the two
dimensional singularity as effectively as the Ridgelet transform.
Statistics in Table II
provides a clear insight in the efficiency of the Ridgelet transform in coding
the Saturn image which has a curved edge. Even though the boundary is curved,
we can very well observe different shades of intensity along straight lines.
This aspect has contributed to the success of Ridgelet over Wavelets. The
tradeoff between Compression ratio and PSNR is very appreciable and encourages
the usage of Ridgelet transforms for astronomical data like the Saturn image. A
set of reconstructed images at various levels of compression have been provided
at the end of this chapter for comparisons. A typical custom made test image of
a Truncated Gaussian function has been found to produce very good results as
seen in Table III, with the proposed compression system though the image has
only one linear singularity, it is well coded by Ridgelets than Wavelets.
The graphs shown in Fig 8, 9
and 10 are a comparison between Ridgelets and Wavelets with compression ratio
along the x-axis and PSNR along the y-axis. It can be clearly seen that the
TABLE III
Comparison results OF TRUNCATED
GAUSSIAN image
|
No. of bit planes excluded |
CR |
RMSE |
PSNR |
|||
|
Proposed scheme |
Existing scheme |
Proposed scheme |
Existing scheme |
Proposed scheme |
Existing scheme |
|
|
6 |
76.0058 |
84.8225 |
22.4090 |
19.6888 |
29.1535 |
25.0650 |
|
5 |
50.8020 |
52.2043 |
22.2336 |
19.3399 |
29.2400 |
25.1430 |
|
4 |
20.9231 |
37.3984 |
21.9716 |
19.3003 |
29.0818 |
25.4659 |
|
3 |
5.7522 |
10.3330 |
21.6816 |
19.1425 |
28.0013 |
25.7351 |
Ridgelets curve is ahead of
the wavelets curve at all points for all the test images considered. A trade
off in the compression ratio achieved by wavelets, to match the PSNR achieved
by the Ridgelets, seems too costly.
Fig 7 CR vs. PSNR
for OBJECT image Fig 8 CR vs. PSNR for SATURN image Fig 9 CR vs. PSNR for TRUNCATED
GAUSSIAN image
The graph shown in Fig 7 clearly indicates the
superiority of the proposed compression technique using Ridgelets with modified SPIHT over the existing wavelet based
method. The high signal content in the proposed method could not be achieved by
the existing method even with a sacrifice in the compression ratio. Also the
curves show an interesting feature about the proposed compression method. For
lower compression ratio range of 5 to 25 we find that the PSNR increases as the
compression ratio increases. This is unlike the existing schemes which show a
decrease in PSNR as the compression ratio increases. The graph is a proof for
the fact that the proposed method is highly suitable for images with straight
edges especially like “object” image. The comparison graph shown in Fig 8 for
the Saturn image reflects high PSNR for the proposed method than the existing
one for all ranges of compression ratios. But another feature to note is that
the PSNR curve doesn’t exhibit the strange behaviour as that of the object
image. It is more a normal behaviour with an increase in the PSNR performance. Fig
9 shows the comparison graph for the truncated Gaussian image. This graph is
more or less similar to the one obtained for object image. The curve for the
proposed technique shows the increase in PSNR as well as the strange behavior
similar to the one seen in Fig 7. This clearly indicates the suitability of the
proposed method for this custom made test image.
Ridgelet Transform Wavelet
Transform
(a)
Reconstructed (b) Reconstructed (c)
Reconstructed (d)
Reconstructed (e) Reconstructed (f) Reconstructed
Image with Image with Image with Image with Image with Image with
CR= 7.5464 CR= 20.8719 CR=
43.8937 CR= 8.3525 CR= 19.1304 CR=
31.5551
Ridgelet
Transform Wavelet
Transform
(g) Reconstructed (h) Reconstructed (i) Reconstructed (j) Reconstructed (k) Reconstructed (l)
Reconstructed
Image with Image with Image
with Image with Image with Image with
CR= 3.6959 CR= 8.4370 CR=
26.0074 CR= 4.3249 CR= 9.5448 CR= 31.2467
Ridgelet Transform Wavelet Transform
(m) Reconstructed (n) Reconstructed (o)
Reconstructed (p) Reconstructed (q) Reconstructed (r) Reconstructed
Image with Image with Image with Image with Image with Image with
CR= 5.7522
CR= 20.9231
CR= 50.8020 CR= 4.1815 CR= 10.3302 CR= 52.2045
Fig 10 Original and Reconstructed Images using
Ridgelet and Wavelet Transform with Modified SPIHT for different Compression
ratios
VI.
Conclusions
The proposed algorithm of
Finite Ridgelet transform combined with Modified SPIHT scheme gave compression
ratios as high as 80:1 with very good PSNR. The results are found to be
comparable with conventional wavelet based compression popularly available in
JPEG 2000 for the Images which are more discontinuous with straight line
singularity and hence this method warrants further investigation. The codec is
characterized by its low computational complexity and the computational speed
of the algorithm is very good than the wavelet based schemes. Experimental
results clearly show that the proposed compression technique results in higher
quality reconstructed images compared to that of other prominent algorithms
operating at similar bit rates for the class of images where edges are dominant
with minimum variation in compression ratio. Thus, we can conclude that FRIT
with modified SPIHT is likely to be among the current state-of-the-art
compression algorithms in terms of visual and computational performance.
VII.
Acknowledgment
The
authors are grateful for the support extended by the Network project funded by
Swiss Development Cooperation towards the completion of this project.
VIII.
References
[1] J. Candes,
“Ridgelets: theory and applications”, Ph.D. thesis, Department of Statistics,
[2] E. J. Candes
and D. L. Donoho, “Ridgelets: a key to
higher-dimensional intermittency", Phil. Trans. R.Soc.
Lond. A., pp. 2495-2509, 1999.
[3] Emmanuel J. Candes,
“Ridgelets and Their Derivatives: Representation of Images with Edges”, Saint Malo Proceedings,
[4] Minh N. Do and Martin
Vetterli, “Orthonormal Finite Ridgelet Transform for Image Compression”, in
proceedings of IEEE International Conference on Image Compressing, Vol. 2, pp.
367-370, September 2000.
[5] Minh N. Do
and Martin Vetterli, “The Finite Ridgelet Transform for Image Representation”,
IEEE Transactions on Image Processing, Vol. 12, No. 1 January 2003.
[6] E. D. Bolker,
“The finite Radon transform", in Integral Geometry (Contemporary
Mathematics, Vol. 63),S. Helgason R. L. Bryant, V. Guillemin and R. O. Wells Jr., Eds., pp. 27-50. 1987.
[7] F. Matus
and J. Flusser, “Image representation via a finite
Radon transform", IEEE Trans. Pattern Anal. Machine Intelligence, vol. 15,
no. 10, pp. 996-1006, Oct 1993.
[8] Aldo
Morales and Sedig Agili,” Implementing the SPIHT Algorithm in MATLAB”, Proceedings of ASEE/WFEO International
Colloquium, 2003.
[9]
A.
Said and W. Pearlman, “A New, fast and Efficient Image Codec based on Set
Partitioning in Hierarchical Trees,” IEEE
Transactions on Circuits and
Systems for Video technology, Vol. 6, No. 3, pp. 243 – 250, June 1996.
[10]
Sayood, Khalid (2000),” Introduction to
Data Compression”, Second edition Morgan Kaufmann, pp. 45-494.
Technical College - Bourgas,